package binary_tree.leetcode.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author bruin_du
 * @description 向下的路径节点之和
 * @date 2022/8/14 21:06
 **/
public class OfferII050_PathSum {
    public int pathSum(TreeNode root, int targetSum) {
        // 方法一：暴力法
        method1(root, targetSum);

        // 方法二：动态规划
        return method2(root, targetSum);
    }

    private int method1(TreeNode root, int targetSum) {
        if (root == null) return 0;
        int num = find(root, targetSum);
        return pathSum(root.left, targetSum) + pathSum(root.right, targetSum) + num;
    }

    int find(TreeNode root, long targetSum) {
        if (root == null) return 0;
        targetSum -= root.val;
        return (targetSum == 0 ? 1 : 0) + find(root.left, targetSum) + find(root.right, targetSum);
    }

    private int method2(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);
        return dfs(root, targetSum, map, 0);
    }

    private int dfs(TreeNode root, int targetSum, Map<Long, Integer> map, long sum) {
        if (root == null) return 0;
        long x = sum + root.val;
        int res = map.getOrDefault(x - targetSum, 0);
        map.put(x, map.getOrDefault(x, 0) + 1);
        int left = dfs(root.left, targetSum, map, x);
        int right = dfs(root.right, targetSum, map, x);
        // 这个结点后的结果遍历完了，将其减去，避免影响其他分支的结果
        map.put(x, map.get(x) - 1);
        return res + left + right;
    }
}
